package cn.dlc.com.graph;

import cn.dlc.com.queue.Queue;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/30 21:06
 * @desc 当前类的描述信息
 */
@Data
public class Digraph {

    // 记录顶点数量
    private final int V;
    // :记录边数量
    private int E;
    // :邻接表队列
    private Queue<Integer>[] adj;

    public Digraph(int V) {
        this.V = V;
        this.E = 0;

        this.adj = new Queue[V];

        // 初始化队列数组
        for (int i = 0; i < V; i++) {
            adj[i] = new Queue<>();
        }

    }

    // :获取图中顶点的数量
    public int V(){
        return this.V;
    }

    // :获取图中边的数量
    public int E(){
        return this.E;
    }

    // 向有向图中添加一条边v->w
    public void addEdge(int v,int w){
        // 添加到链表里面;只需要让顶点w出现在顶点v的邻接表中﹐因为边是有方向的﹐
        adj[v].enQueue(w);
        this.E++;
    }

    //获取由v指出的边所连接的所有顶点(获取邻接链表)
    public Queue<Integer> adj(int v){
        return this.adj[v];
    }

    // 该图的反向图
    private Digraph reverse(){
        // 创建一个反的图
        Digraph revers = new Digraph(this.V);

        // 获取所有的顶点（顶点为0-v的数字，所以这样遍历）
        for (int i = 0; i < this.V; i++) {
            // 获取所有邻接点
            for (Integer w : adj[i]) {
                // 将邻接点作为顶点，顶点作为邻接点
                revers.addEdge(w, i);
            }
        }
        return revers;
    }
}
